'''
Created on 30/09/2013

@author: daniel
'''
import unittest
import colecciones.cola

class MinHeap(colecciones.cola.Cola):
    '''
    clase concreta que se asocia a la clase Heap para lograr una estructura de
    ordenamiento del tipo minheap
    '''
    def agregar(self,elem):
        self.poner(elem)
        iHijo=self.getTamanio()
        while(self.__esMinHeap__()==False):
            iPadre=(iHijo//2)
            if(elem.__cmp__(self.__datos__.elemento(iPadre-1))<0):
                aux=self.__datos__.elemento(iPadre-1)
                self.__datos__.agregar(self.__datos__.elemento(iHijo-1),iPadre-1)#guardo hijo en el lugar del padre
                self.__datos__.eliminar(iPadre)
                self.__datos__.agregar(aux,iHijo-1)#guardo padre en el lugar del hijo
                self.__datos__.eliminar(iHijo)
            iHijo=iPadre
        
    def eliminar(self):
        elem=self.sacar()
#         print self.__datos__.elemento(self.getTamanio()-1)
        self.__datos__.agregar(self.__datos__.eliminar(self.getTamanio()-1), 0)
        iPadre=1
        while(self.__esMinHeap__()==False):
            iHijoR=(iPadre*2)+1
            iHijoL=iPadre*2
#             print self.__datos__
            if self.getTamanio()==2:
                aux=self.__datos__.elemento(0)
                self.__datos__.agregar(self.__datos__.elemento(1),0)#guardo hijo en el lugar del padre
                self.__datos__.eliminar(0)
                self.__datos__.agregar(aux,1)#guardo padre en el lugar del hijo
                self.__datos__.eliminar(2)
            elif(self.__datos__.elemento(iHijoR-1).__cmp__(self.__datos__.elemento(iHijoL-1))>0):
                aux=self.__datos__.elemento(iPadre-1)
                self.__datos__.agregar(self.__datos__.elemento(iHijoL-1),iPadre-1)#guardo hijo en el lugar del padre
                self.__datos__.eliminar(iPadre)
                self.__datos__.agregar(aux,iHijoL-1)#guardo padre en el lugar del hijo
                self.__datos__.eliminar(iHijoL)
                iPadre=iHijoL
            else:
                aux=self.__datos__.elemento(iPadre-1)
                self.__datos__.agregar(self.__datos__.elemento(iHijoR-1),iPadre-1)#guardo hijo en el lugar del padre
                self.__datos__.eliminar(iPadre)
                self.__datos__.agregar(aux,iHijoR-1)#guardo padre en el lugar del hijo
                self.__datos__.eliminar(iHijoR)
                iPadre=iHijoR
        return elem
    

    def __esMinHeap__(self):
        if(self.getTamanio()<=1):return True
        if(self.getTamanio()==2):
            if(self.__datos__.elemento(1).__cmp__(self.__datos__.elemento(0))<0):
                return False
            else: return True
        i=2
        while(i-1<self.getTamanio()):
#             print self.getTamanio()
            if(self.__datos__.elemento(i-1).__cmp__(self.__datos__.elemento((i//2)-1))<0):
                return False
            i+=1
        return True
    
    def __str__(self):
        return self.__datos__.__str__()


class Test(unittest.TestCase):

    def testInit(self):
        self.assertIsInstance(MinHeap(), MinHeap, "Verifica la creacion de minHeap")
    def testPoner(self):
        obj=MinHeap()
        obj.poner(23)
        self.assertFalse(obj.esVacia(), "verifica existencia de elemento")
    
    def testTope(self):
        obj=MinHeap()
        obj.poner(1)
        obj.poner(2)
        obj.poner(3)
        self.assertEquals(obj.tope(),1, "verifica existencia del dato")
    
    def testSacar(self):
        obj=MinHeap()
        obj.poner(5)
        obj.poner(10)
        self.assertFalse(obj.esVacia(), "verifica existencia de elemento")
        elim=obj.sacar()
        self.assertFalse(obj.esVacia(), "verifica la no existencia de elemento")
        self.assertEquals(elim, 5,"elemento eliminado")
    
    def testEsVacia(self):
        obj=MinHeap()
        self.assertTrue(obj.esVacia(), "Verifica devolucion correcta")
        obj.poner(1)
        self.assertFalse(obj.esVacia(), "Verifica devolucion correcta")
    
    def testIncluye(self):
        obj=MinHeap()
        obj.poner(1)
        obj.poner(2)
        obj.poner(3)
        self.assertTrue(obj.__datos__.incluye(2), "Verifica devolucion correcta")
        self.assertFalse(obj.__datos__.incluye(4), "Verifica devolucion correcta")

    def testGetTamanio(self):
        obj=MinHeap()
        obj.poner(1)
        obj.poner(2)
        obj.poner(3)
        self.assertTrue(obj.__datos__.getTamanio()==3,"Verifica devolucion correcta del tamanio")
    
    def testEsMinHeap(self):
        obj1=MinHeap()
        obj1.poner(52)
        obj1.poner(41)
        self.assertFalse(obj1.__esMinHeap__(), "Verifica correcto no maxheap")
        
        obj=MinHeap()
        obj.poner(54)
        obj.poner(52)
        obj.poner(41)
        obj.poner(50)
        obj.poner(52)
        self.assertFalse(obj.__esMinHeap__(),"Verifica correcta devolucion de la funcion")

        obj2=MinHeap()
        obj2.poner(41)
        obj2.poner(46)
        obj2.poner(50)
        obj2.poner(52)
        obj2.poner(54)
        self.assertTrue(obj2.__esMinHeap__(),"Verifica correcta devolucion de la funcion")

        obj3=MinHeap()
        obj3.poner(10)
        obj3.poner(50)
        obj3.poner(30)
        obj3.poner(400)
        obj3.poner(200)
        obj3.poner(31)
        obj3.poner(40)
        self.assertTrue(obj3.__esMinHeap__(),"Verifica correcta devolucion de la funcion")

        obj4=MinHeap()
        obj4.poner(10)
        obj4.poner(10)
        obj4.poner(10)
        self.assertTrue(obj4.__esMinHeap__(),"Verifica correcta devolucion de la funcion")


if __name__ == "__main__":
    #import sys;sys.argv = ['', 'Test.testName']
    unittest.main()